In many fields of information processing, data at one place in a system (for instance, data sent from the far end of a communication link) should be identical to data at another place in the system (for instance, data received at the near end of a communication link). Various means have been devised to determine that two pieces of data are in fact identical. One common way is to generate a digital signature for each data object, and then to compare the signatures. (A digital signature is a comparatively short string of bits produced by applying a fixed algorithm to a longer piece of digital data; many different digital signature algorithms are known to practitioners.) Since digital signatures are much smaller than the objects they represent, they can be transmitted and compared quickly and reliably.
It is important, of course, to design digital signature algorithms so that the most likely changes to data objects are reflected in changes to their signatures; there is much art in this field. For instance, U.S. Pat. Nos. 4,881,264 (to Merkle) and 5,097,504 (to Camion et al.) both describe ways to verify that a particular data object has not been altered by using one or more digital signatures in the verification.
Various forms of malicious software (including "computer viruses" and other "Trojan Horses") operate by surreptitiously altering software objects in an attacked system. The problem of discovering such changes is somewhat different from simply determining whether two data objects are in fact identical, because in a system various legitimate activities also make changes to objects over time. Therefore, there is a need for methods that can differentiate legitimate changes in a system from malicious ones.
The traditional approach to detecting such undesirable changes involves computing and storing a digital signature or signatures for each object to be protected, and periodically recomputing the signature(s) and comparing to the previous value. Objects for which the signature information has changed are judged to have been altered, and the user is alerted to the fact. The primary weakness of these methods is that they typically tell the user only which files have changed, and the user must judge whether or not the change was legitimate. The differentiation of legitimate from malicious changes cannot be done simply by detecting that some change has in fact occurred.
In general, a "malicious" change is one that is done without the knowledge or consent of the data owner, typical by a computer virus or similar unauthorized program. A "legitimate" change is one that results from some intentional action of the data owner, such as upgrading to a new level of software, or making configuration changes to some application program which stores configuration data internally.